/*
 * @lc app=leetcode.cn id=46 lang=cpp
 *
 * [46] 全排列
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public: 
    vector<int> array;              // 保存当前的排列
    vector<vector<int>> arrays;     // 保存所有的排列

    vector<vector<int>> permute(vector<int>& nums) {
        arrange(nums);
        return arrays;
    }


    void arrange(vector<int>& nums) {
        // 当前排列已满，保存至结果
        if (array.size() == nums.size()) {
            arrays.push_back(array);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // 寻找一个未经访问的节点，-1表示已经访问
            int num = nums[i];
            if (num == -11) continue;
            
            nums[i] = -11;
            array.push_back(num);

            arrange(nums);

            array.pop_back();
            nums[i] = num;
        }
        
        return;
    }
};
// @lc code=end

